home *** CD-ROM | disk | FTP | other *** search
/ McDisk 1 / McDisk 1.adf / sources / root-routine.c < prev   
Encoding:
Text File  |  1978-04-12  |  2.2 KB  |  116 lines
  1.                           A very fast root-routine!
  2.  
  3. This  C-Sources  show  the  way to the fastes root-routine as described in the
  4. article  in  this  McDisk.   I found this routines in the german paper-mag C`T
  5. 1/90.  The routine was developed by Otto Peter.  If you need a root-routine in
  6. assembler, risk a look at the other sources on this Disk.
  7.  
  8. The different sources show the optimition in 5 steps.  Just take the last one,
  9. cause it`s the fastes!
  10.  
  11.  
  12.  
  13. #define N_BITS 32
  14. #define MAX_BIT ((N_BITS + 1) / 2 - 1)
  15.  
  16. unsigned long int sqrt_1(x)
  17.   unsigned long int x;
  18.   {
  19.   register int i;
  20.   register unsigned long int m, r, root;
  21.  
  22.   root = 0;  m = 1 << MAX_BIT
  23.   for (i = MAX_BIT;  i >= 0;  i--)
  24.     {
  25.     r = root + m;
  26.     if (r * r <= X) root = r;
  27.     m >>= 1;                                /* same as  m = m/2 */
  28.     }
  29.   return root;
  30.   }
  31.  
  32.  
  33. unsigned long int sqrt_2(x)
  34.   unsigned long int x;
  35.   {
  36.   register long int i;
  37.   register unsigned long int m, r2, root;
  38.   unsigned long int root2;
  39.  
  40.   root2 = root = 0;  m = 1 << MAX_BIT;
  41.   for (i = MAX_BIT;  i >= 0;  i--)
  42.     {
  43.     r2 = root2 + (root << i + 1)  +  (1 << i + i);
  44.     if (r2 <= X)
  45.       {
  46.       root2 = r2;  root += m;
  47.       }
  48.     m >>= 1;
  49.     }
  50.   return root;
  51.   }
  52.  
  53.  
  54. unsigned long int sqrt_3(x)
  55.   unsigned long int x;
  56.   {
  57.   register unsigned long int m2, r2, xroot, root2;
  58.   int i;
  59.  
  60.   root2 = xroot = 0;  m2 = 1 << MAX_BIT * 2;
  61.   for (i = MAX_BIT;  i >= 0;  i--)
  62.     {
  63.     r2 = root2 + xroot + m2;
  64.     xroot >>= 1;
  65.     if (r2 <= X)
  66.       {
  67.       root2 = r2;  xroot += m2;
  68.       }
  69.     m2 >>= 2;
  70.     }
  71.   return xroot;
  72.   }
  73.  
  74.  
  75. unsigned long int sqrt_4(x)
  76.   unsigned long int x;
  77.   {
  78.   register unsigned long int xroot, m2, x2;
  79.  
  80.   xroot = 0;  m2 = 1 << MAX_BIT * 2;
  81.   do
  82.     {
  83.     x2 = xroot + m2;
  84.     xroot >>= 1;
  85.     if (x2 <= X)
  86.       {
  87.       x -= x2;  xroot += m2;
  88.       }
  89.     }
  90.   while (m2 >>= 2);
  91.   return xroot;
  92.   }
  93.  
  94.  
  95. unsigned long int sqrt_5(x)
  96.   unsigned long int x;
  97.   {
  98.   register unsigned long int xroot, m2, x2;
  99.  
  100.   xroot = 0;  m2 = 1 << MAX_BIT * 2;
  101.   do
  102.     {
  103.     x2 = xroot + m2;
  104.     xroot >>= 1;
  105.     if (x2 <= X)
  106.       {
  107.       x -= x2;  xroot += m2;
  108.       }
  109.     }
  110.   while (m2 >>= 2);
  111.   if (xroot < x) return xroot + 1;
  112.   return xroot;
  113.   }
  114.  
  115.  
  116.